package common

import (
	"errors"
	"hash/crc32"
	"sort"
	"strconv"
	"sync"
)

// 一致性哈希

// 定义新的数据类型，支持sort接口
type uints []uint32   //对hash值得排序
// 实现sort接口
// type SortBy []Type
// func (a SortBy) Len() int           { return len(a) }
// func (a SortBy) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
// func (a SortBy) Less(i, j int) bool { ret

func (x uints) Len() int {return len(x)}
func (x uints) Less(i,j int) bool {
	return x[i]<x[j]
}
func (x uints) Swap(i,j int) {
	x[i],x[j] = x[j],x[i]
}

var errEmpty = errors.New("hash circle no data")

// 一致性哈希  结构体
type ConsistentHash struct{
	// 哈希环
	hashCircle map[uint32]string   // key-哈希值
	// 定义新的结构uints 为了支持sort接口
	sortedHashes uints   //已经排序好的
	// 虚拟节点  每一个真实节点对应几个虚拟节点  为了均衡
	VirtualNode int
	sync.RWMutex
}
func NewConsistentHash() *ConsistentHash {
	return &ConsistentHash{
		hashCircle: make(map[uint32]string),
		VirtualNode: 20,
	}
}

func (c *ConsistentHash) Add(elem string) {
	c.Lock()
	defer c.Unlock()
	//写锁
	c.add(elem)
}
// Remove 删除一个节点
func (c *ConsistentHash) Remove(element string) {
	c.Lock()
	defer c.Unlock()
	c.remove(element)
}
// Get 根据数据标示获取最近的服务器节点信息
func (c *ConsistentHash) Get(name string) (string, error) {
	c.RLock()               //添加锁
	defer c.RUnlock()       //解锁
	if len(c.hashCircle) == 0 { //如果为零则返回错误
		return "", errEmpty
	}
	key := c.hashKey(name) //计算hash值
	i := c.search(key)
	return c.hashCircle[c.sortedHashes[i]], nil
}

// 自动生成key值
func (c *ConsistentHash) generateKey(element string, index int) string {
	return element + strconv.Itoa(index)
}
// 添加节点
func (c *ConsistentHash) add(element string) {
	for i := 0; i < c.VirtualNode; i++ { //循环虚拟节点，设置副本
		c.hashCircle[c.hashKey(c.generateKey(element, i))] = element //根据生成的节点添加到hash环中
	}
	c.updateSortedHashes() //更新排序
}
// 获取hash位置
func (c *ConsistentHash) hashKey(key string) uint32 {
	if len(key) < 64 {
		var scratch [64]byte                          //声明一个数组长度为64
		copy(scratch[:], key)                         //拷贝数据到数组中
		return crc32.ChecksumIEEE(scratch[:len(key)]) //使用IEEE 多项式返回数据的CRC-32校验和
	}
	return crc32.ChecksumIEEE([]byte(key))
}
// 更新排序，方便查找
func (c *ConsistentHash) updateSortedHashes() {
	hashes := c.sortedHashes[:0]
	if cap(c.sortedHashes)/(c.VirtualNode*4) > len(c.hashCircle) { //判断切片容量，是否过大，如果过大则重置
		hashes = nil
	}
	for k := range c.hashCircle { //添加hashes
		hashes = append(hashes, k)
	}
	sort.Sort(hashes)       //对所有节点hash值进行排序，方便之后进行二分查找
	c.sortedHashes = hashes //重新赋值
}
//删除节点
func (c *ConsistentHash) remove(element string) {
	for i := 0; i < c.VirtualNode; i++ {
		delete(c.hashCircle, c.hashKey(c.generateKey(element, i)))
	}
	c.updateSortedHashes()
}
//顺时针查找最近的节点
func (c *ConsistentHash) search(key uint32) int {
	//查找算法
	f := func(x int) bool {
		return c.sortedHashes[x] > key
	}
	i := sort.Search(len(c.sortedHashes), f) //使用"二分查找"算法来搜索指定切片满足条件的最小值
	if i >= len(c.sortedHashes) {            //如果超出范围则设置i=0
		i = 0
	}
	return i
}
